package lhc.alg.top100;

/**
 * description: https://leetcode.cn/problems/reverse-nodes-in-k-group/
 *  K 个一组翻转链表
 * author: hongchen.liao
 * date:  2022/9/18
 */
public class _25_ {


     //Definition for singly-linked list.
     public class ListNode {
         int val;
         ListNode next;
         ListNode() {}
         ListNode(int val) { this.val = val; }
         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     }

    class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
            ListNode hair = new ListNode(-1, head);
            ListNode pre = hair;
            while(head != null){
                ListNode tail = pre;
                for(int i = 0; i < k; i++){
                    tail = tail.next;
                    if(tail == null){
                        return hair.next;
                    }
                }
                ListNode nxt = tail.next;
                ListNode[] ln = reverseK(head, tail);
                head = ln[0];
                tail = ln[1];

                pre.next = head;
                tail.next = nxt;

                pre = tail;
                head = tail.next;
            }
            return hair.next;
        }

        ListNode[] reverseK(ListNode head, ListNode tail){
            ListNode prev = tail.next, p = head;
            while(prev != tail){
                ListNode t = p.next;
                p.next = prev;
                prev = p;
                p = t;
            }
            return new ListNode[]{tail, head};
        }
    }


}
